#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
#include <unordered_map>

using namespace std;

struct EdgeTime {
    int u;
    int v;
    int inT;
    int outT;
};

struct OverloadEvent {
    int road_id;
    int start_time;
    int end_time;
    int excess;
};

vector<int> dijkstra(const vector<vector<int>>& graph, int start, int end) {
    int N = graph.size();
    vector<int> distance(N, INT_MAX);
    vector<int> predecessor(N, -1);
    vector<bool> visited(N, false);
    distance[start] = 0;

    for (int i = 0; i < N; ++i) {
        int u = -1;
        int min_distance = INT_MAX;
        for (int j = 0; j < N; ++j) {
            if (!visited[j] && distance[j] < min_distance) {
                min_distance = distance[j];
                u = j;
            }
        }
        if (u == -1) break;
        if (u == end) break;
        visited[u] = true;
        for (int v = 0; v < N; ++v) {
            if (!visited[v] && graph[u][v] != INT_MAX && distance[u] + graph[u][v] < distance[v]) {
                distance[v] = distance[u] + graph[u][v];
                predecessor[v] = u;
            }
        }
    }

    vector<int> path;
    int node = end;
    while (node != -1) {
        path.push_back(node);
        node = predecessor[node];
    }
    reverse(path.begin(), path.end());
    return path;
}

int get_road_id(int u, int v, int N) {
    return min(u, v) * N + max(u, v);
}

vector<int> find_alternative_path(const vector<vector<int>>& graph, int start, int end, const vector<int>& forbidden_roads, int N) {
    vector<vector<int>> new_graph = graph;
    for (int road : forbidden_roads) {
        int u = road / N;
        int v = road % N;
        new_graph[u][v] = INT_MAX;
        new_graph[v][u] = INT_MAX;
    }
    return dijkstra(new_graph, start, end);
}

bool check_flow(const unordered_map<int, vector<pair<int, int>>>& road_events, const unordered_map<int, int>& road_capacity, vector<OverloadEvent>& overload_events, int N) {
    overload_events.clear();
    for (auto& road_entry : road_events) {
        int road_id = road_entry.first;
        vector<pair<int, int>>& events = road_entry.second;
        sort(events.begin(), events.end(), [](const pair<int, int>& a, const pair<int, int>& b) {
            if (a.first == b.first) {
                return a.second > b.second; // enter (+1) before leave (-1)
            }
            return a.first < b.first;
        });
        int current_count = 0;
        int capacity = road_capacity[road_id];
        int start_excess = -1;
        for (auto& event : events) {
            int time = event.first;
            int delta = event.second;
            if (current_count > capacity) {
                if (start_excess == -1) {
                    start_excess = time;
                }
            } else {
                if (start_excess != -1) {
                    overload_events.push_back({road_id, start_excess, time, current_count - capacity});
                    start_excess = -1;
                }
            }
            current_count += delta;
        }
        if (start_excess != -1) {
            int max_time = 0;
            for (auto& car : times) {
                for (auto& et : car) {
                    if (et.outT > max_time) {
                        max_time = et.outT;
                    }
                }
            }
            overload_events.push_back({road_id, start_excess, max_time, current_count - capacity});
        }
    }
    return overload_events.empty();
}

int main() {
    int N, M;
    cin >> N >> M;

    vector<vector<int>> graph(N, vector<int>(N, INT_MAX));
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            int val;
            cin >> val;
            if (val == 0 && i != j) {
                graph[i][j] = INT_MAX;
            } else {
                graph[i][j] = val;
            }
        }
    }

    vector<vector<int>> restrictions(N, vector<int>(N));
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            cin >> restrictions[i][j];
        }
    }

    unordered_map<int, int> road_capacity;
    unordered_map<int, pair<int, int>> road_map;
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            if (i != j) {
                int cap = restrictions[i][j];
                int road_id = get_road_id(i, j, N);
                road_capacity[road_id] = cap;
                road_map[road_id] = make_pair(i, j);
            }
        }
    }

    vector<pair<int, int>> cars(M);
    for (int i = 0; i < M; ++i) {
        int start, end;
        cin >> start >> end;
        cars[i] = make_pair(start - 1, end - 1); // 转换为0-based索引
    }

    vector<vector<int>> paths(M);
    vector<vector<EdgeTime>> times(M); // 存储每辆车每段路的时间信息
    int total_time = 0;

    unordered_map<int, vector<pair<int, int>>> road_events;

    for (int car_id = 0; car_id < M; ++car_id) {
        int start = cars[car_id].first;
        int end = cars[car_id].second;
        paths[car_id] = dijkstra(graph, start, end);

        int current_time = 0;
        for (int j = 0; j < paths[car_id].size() - 1; ++j) {
            int u = paths[car_id][j];
            int v = paths[car_id][j + 1];
            int road_length = graph[u][v];
            EdgeTime et = {u + 1, v + 1, current_time, current_time + road_length};
            times[car_id].push_back(et);
            int road_id = get_road_id(u, v, N);
            road_events[road_id].push_back(make_pair(current_time, +1));
            road_events[road_id].push_back(make_pair(current_time + road_length, -1));
            current_time += road_length;
            total_time += road_length;
        }
    }

    vector<OverloadEvent> overload_events;

    while (!check_flow(road_events, road_capacity, overload_events, N)) {
        if (overload_events.empty()) {
            break; // 没有超过流量限制
        }
        sort(overload_events.begin(), overload_events.end(), [](const OverloadEvent& a, const OverloadEvent& b) {
            return a.excess > b.excess;
        });
        OverloadEvent event = overload_events.front();
        int road_id = event.road_id;
        int start_time = event.start_time;
        int end_time = event.end_time;

        vector<int> cars_on_road;
        for (int car_id = 0; car_id < M; ++car_id) {
            for (auto& et : times[car_id]) {
                int u = et.u - 1;
                int v = et.v - 1;
                int current_road_id = get_road_id(u, v, N);
                if (current_road_id == road_id && et.inT < end_time && et.outT > start_time) {
                    cars_on_road.push_back(car_id);
                    break;
                }
            }
        }

        for (int car_id : cars_on_road) {
            vector<int> current_path = paths[car_id];
            vector<EdgeTime> current_times = times[car_id];

            vector<int> forbidden_roads = {road_id};

            vector<int> new_path = find_alternative_path(graph, cars[car_id].first, cars[car_id].second, forbidden_roads, N);
            if (!new_path.empty()) {
                // 移除旧路径的时间事件
                for (int j = 0; j < current_path.size() - 1; ++j) {
                    int u = current_path[j];
                    int v = current_path[j + 1];
                    int road_id_old = get_road_id(u, v, N);
                    road_events[road_id_old].erase(remove_if(road_events[road_id_old].begin(), road_events[road_id_old].end(), [current_times](const pair<int, int>& event) {
                        for (auto& et : current_times) {
                            if (event.first >= et.inT && event.first < et.outT) {
                                return true;
                            }
                        }
                        return false;
                    }), road_events[road_id_old].end());
                }

                // 更新路径和时间信息
                paths[car_id] = new_path;
                times[car_id].clear();
                int current_time = 0;
                for (int j = 0; j < new_path.size() - 1; ++j) {
                    int u = new_path[j];
                    int v = new_path[j + 1];
                    int road_length = graph[u][v];
                    EdgeTime et = {u + 1, v + 1, current_time, current_time + road_length};
                    times[car_id].push_back(et);
                    int road_id_new = get_road_id(u, v, N);
                    road_events[road_id_new].push_back(make_pair(current_time, +1));
                    road_events[road_id_new].push_back(make_pair(current_time + road_length, -1));
                    current_time += road_length;
                    total_time += road_length;
                }
                break; // 成功调整一辆车，重新检查流量限制
            }
        }
    }

    if (check_flow(road_events, road_capacity, overload_events, N)) {
        // 输出路径和时间信息
        for (int i = 0; i < M; ++i) {
            cout << "车辆" << (i + 1) << ":" << endl;
            cout << "路径: ";
            for (int node : paths[i]) {
                cout << node + 1 << " ";
            }
            cout << endl;
            cout << "时间:" << endl;
            for (int j = 0; j < times[i].size(); ++j) {
                cout << "(" << times[i][j].u << ", " << times[i][j].v << ", " << times[i][j].inT << ", " << times[i][j].outT << ")" << endl;
            }
            cout << "总时间: " << times[i].back().outT << endl;
            cout << endl;
        }
        cout << "所有车辆的总行驶时间: " << total_time << endl;
    } else {
        cout << "无法满足流量限制，请调整路径规划。" << endl;
    }

    return 0;
}